package LinkedList;

import java.util.HashSet;
import java.util.Set;

class Node{
    long val;
    Node prev;
    Node next;

    public Node(long val) {
        this.val = val;
    }
}


public class LinkedList {

    // 合并两个有序链表(递归)
    public static Node merge(Node head1,Node head2){
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        if(head1.val < head2.val){
            head1.next = merge(head1.next,head2);
            return head1;
        }
        head2.next = merge(head1,head2.next);
        return head2;
    }
    // 合并两个有序链表 （loop）
    public static Node merge_Loop(Node head1,Node head2){
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        Node fake_head = new Node(-1);
        Node cur = fake_head;

        while(head1 != null || head2 != null){
            if(head1.val < head2.val){
                cur.next = head1;
                head1 = head1.next;
            }else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }

        while(head1 != null){
            cur.next = head1;
            head1 = head1.next;
            cur = cur.next;
        }

        while(head2 != null){
            cur.next = head2;
            head2 = head2.next;
            cur = cur.next;
        }
        return fake_head.next;
    }

    // 获取链表的中间节点(偶数返回 靠后的node)
    public static Node getMid(Node head){
        if(head == null) return null;
        Node slow = head;
        Node fast = head;

        while(fast != null){
            fast = fast.next;
            if(fast == null) break;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    // 获取倒数第 K 个节点
    public static Node getBack_k(Node head,int k){
        if(head == null) return null;
        Node ans = head;
        Node next_k = head;
        // ans -> * -> * -> * -> * -> next_k  -> * ->*; // 以相同的速度保持 距离差
        while(next_k != null && k > 0){
            next_k = next_k.next;
            k--;
        }
        if(k > 0) return ans;
        for(;next_k != null; next_k = next_k.next){
            ans = ans.next;
        }
        return ans;
    }

    // 删除排序链表中重复节点
    public static Node deleteSame(Node head){
        // 删除链表中相同的元素(一个不留)
        if(head == null) return null;
        Node fake_head = new Node(-1);
        fake_head.next = head;
        Node pre = fake_head;
        Node cur = head;
        Node next = cur.next;

        while(next != null) {
            while (next != null && cur.val == next.val) {
                next = next.next;
            }
            if (cur.next == next) {
                pre = cur;
                if(next != null) cur = cur.next;
            } else {
                pre.next = next;
                cur = next;
                if(next != null) next = next.next;
            }
        }
        return fake_head.next;
    }

    // 删除无序链表中 重复节点
    public static Node removeSame(Node head){
        if(head == null) return null;
        Set<Long> set = new HashSet<>();
        Node fake_head = new Node(-1);
        fake_head.next = head;
        Node cur = head;
        Node pre = fake_head;

        for(;cur != null ; cur = cur.next){
            if(set.contains(cur.val)){
                pre.next = cur.next;
            }else {
                set.add(cur.val);
                pre = pre.next;
            }
        }
        return fake_head.next;
    }

    public static Node SortByTag(Node head,long target){
        if(head == null) return null;
        Node fake_head = new Node(-1);
        Node cur = head;
        Node next = null;

        while(cur != null){
            next = cur.next;
            cur.next = null;
            if(cur.val < target){
                headInsert(fake_head,cur);
            }else {
                tailInsert(fake_head,cur);
            }
            cur = next;
        }
        return fake_head.next;
    }

    // 插小的 (保证head ！= null)
    private static void headInsert(Node head,Node node){
        Node next = head.next;
        head.next = node;
        node.next = next;
    }

    //插大的
    private static void tailInsert(Node head,Node node){
        Node cur = head;
        Node pre = null;
        while(cur != null){
            pre = cur;
            cur = cur.next;
        }
        if(pre == null){
            head.next = node;
            return ;
        }
        pre.next = node;
        return ;
    }
}




















